/**
 * 84. 柱状图中最大的矩形
 *
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为1 。
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 *
 * 示例 1:
 * https://assets.leetcode.com/uploads/2021/01/04/histogram.jpg
 * 输入：heights = [2,1,5,6,2,3]
 * 输出：10
 * 解释：最大的矩形为图中红色区域，面积为 10
 *
 * 示例 2：
 * https://assets.leetcode.com/uploads/2021/01/04/histogram-1.jpg
 * 输入： heights = [2,4]
 * 输出： 4
 */

function largestRectangleAreaOn2(heights: number[]): number {
	let maxArea = 0
	const len = heights.length
	for (let i = 0; i < heights.length; i++) {
		let left = i - 1,
			right = i + 1
		while (left >= 0 && heights[left] >= heights[i]) {
			left--
		}
		while (right < len && heights[right] >= heights[i]) {
			right++
		}

		maxArea = Math.max(maxArea, (right - left - 1) * heights[i])
	}
	return maxArea
}

function largestRectangleArea(heights: number[]): number {
	let maxArea = 0
	const stack: number[] = []
	heights = [0, ...heights, 0]
	for (let i = 0; i < heights.length; i++) {
		while (stack.length && heights[stack[stack.length - 1]] > heights[i]) {
			maxArea = Math.max(
				maxArea,
				heights[stack.pop()!] * (i - stack[stack.length - 1] - 1)
			)
		}
		stack.push(i)
	}
	return maxArea
}
